

#include "stdio.h"
#include "conio.h"
typedef int DataType;
typedef struct node
{ DataType info;
  struct node *link;
}Node,*Stack;

InitStack(Stack *p)
{
  Stack q;
  q =(Stack)malloc(sizeof(Node));
  q->link=NULL;
  *p = q;

}

Push(Stack H,DataType x)
{
  Stack q;
  q =(Stack)malloc(sizeof(Node));
  q->info=x;
  q->link=H->link;
  H->link=q;

}

Pop(Stack H)
{
   Stack q;
  q = H->link;
  H->link=H->link->link;
  free(q);

}



DataType Top(Stack H)
{
   return H->link->info;
}

int EmptyStack(Stack H)
{
  if(H->link==NULL)
    return 1;
  else
    return 0;
}

int calexp(char *expr)
{
   Stack S;
   DataType x,y,z;
   InitStack(&S);
   while(*expr!='\0')
    { if(*expr>='0' && *expr<='9')
        { Push(S,*expr-'0');expr++;}
      else
        { x=Top(S);Pop(S);
          y=Top(S);Pop(S);
          switch(*expr)
            { case '+':z=y+x;break;
              case '-':z=y-x;break;
              case '*':z=y*x;break;
              case '/':z=y/x;break;
            }
           Push(S,z);
           expr++;
        }
     }
  return Top(S);
}
void infix2postfix(char *inExp)
{

    char *postExp,num=0,i;
    Stack symbol;
    InitStack(&symbol);
    while(*inExp!=NULL)
    {

        if(*inExp>='0'&&*inExp<='9')
        {

            *(postExp+num)=*inExp;     /*digital */
            num++;

        }else{                         /*symbol   */

            if(*inExp==')')
            {
                while(Top(symbol)!='(')
                {
                    *(postExp+num)=symbol->link->info;
                    num++;
                    Pop(symbol);

                }
                Pop(symbol);
            }
            else if(Top(symbol)=='('||Top(symbol)==NULL||*inExp=='(')
            {

                Push(symbol,*inExp);



            }
            else if(*inExp=='+')
            {

                while(Top(symbol)!='('&&Top(symbol)!=NULL)
                {

                    *(postExp+num)=Top(symbol);
                    num++;
                    Pop(symbol);

                }

                Push(symbol,'+');
            }
            else if(*inExp=='*')
            {
                if(Top(symbol)=='*')
                {
                    *(postExp+num)='*';
                    num++;
                }
                else 
                {
                    Push(symbol,'*');
                }


            }
        }
        inExp++;
    }

    while(!EmptyStack(symbol))
    {
        *(postExp+num)=Top(symbol);
        num++;
        Pop(symbol);
    }
    printf("2+3*4+(5*6+7)*8\npostfix:  ");
    for(i=0;i<num;i++)
        printf("%c",*(postExp+i));

     printf("\nresult:   %d",calexp(postExp));

}
void main()
{
    char exp[]="2+3*4+(5*6+7)*8";
    infix2postfix(exp);

    getch();
    return;
}


